#include "exp_2.h"
typedef struct {
    int data[N];
    int top; //栈顶指针
} stack;

void stack_init(stack *s) {
    for (int i = 0; i < N; ++i) {
        s->data[i] = -1;
        s->top = -1;
    }
}

void stack_pop(stack *s) {
    if (s->top != -1)
        --s->top;
}

void stack_push(stack *s, int e) { s->data[++s->top] = e; }

BOOL stack_full(stack *s) { return s->top == N - 1; }

BOOL stack_empty(stack *s) { return s->top == -1; }

void printAnswer(stack *s) {
    for (int i = 0; i < N; ++i) {
        for (int j = 0; j < N; ++j) {
            if (s->data[i] == j) {
                putchar(QUEEN);
                putchar(' ');
            } else {
                putchar(BLANK);
                putchar(' ');
            }
        }
        putchar('\n');
    }
    putchar('\n');
}

void solve8Quees_nonRecurion() {
    BOOL rows[N], cols[N], dias1[N * 2 - 1], dias2[N * 2 - 1];
    int row, col, dia1, dia2;
    int time = 1;
    int i, j;
    stack s;
    stack_init(&s);
    stack_push(&s, 0); //从第一行第一列开始选
    BOOL occupied;
    for (i = 0; i < N; ++i) {
        rows[i] = FALSE;
        cols[i] = FALSE;
    }
    for (i = 0; i < N * 2 - 1; ++i) {
        dias1[i] = FALSE;
        dias2[i] = FALSE;
    }
    while (1) {
        while (1) {
            row = s.top;
            col = s.data[s.top];
            dia1 = s.top - s.data[s.top] + N - 1;
            dia2 = s.top + s.data[s.top];
            // s.top是row，s.data[s.top]是col
            occupied = rows[row] || cols[col] || dias1[dia1] || dias2[dia2];
            if (s.data[s.top] < N && occupied) {
                ++s.data[s.top]; //尝试这一行的下一列
            } else {
                break;
            }
        }
        if (s.data[s.top] < N) {
            if (stack_full(&s)) {
                printf("解法 %d：\n", time);
                printAnswer(&s);
                ++time;
            } else {
                rows[s.top] = TRUE;
                cols[s.data[s.top]] = TRUE;
                dias1[s.top - s.data[s.top] + N - 1] = TRUE;
                dias2[s.top + s.data[s.top]] = TRUE;
                stack_push(&s, -1);
            }
        } else {
            stack_pop(&s);
            //st为空时不需要修改
            if (!stack_empty(&s)) {
                rows[s.top] = FALSE;
                cols[s.data[s.top]] = FALSE;
                dias1[s.top - s.data[s.top] + N - 1] = FALSE;
                dias2[s.top + s.data[s.top]] = FALSE;
            }
        }
        //栈空则推出
        if (!stack_empty(&s)) {
            ++s.data[s.top];
        }else{
            break;
        }
    }
}